package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-16 14:41
 **/
public class LeetCode210 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //图
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<>();
        }

        //入度表
        int[] inDeg = new int[numCourses];
        //向图中添加边
        for (int[] prerequisite : prerequisites) {
            g[prerequisite[1]].add(prerequisite[0]);
            ++inDeg[prerequisite[0]];
        }

        //队列维护入度为0的顶点
        Queue<Integer> q = new LinkedList<>();
        //把所有入度为0的点加入到队列中
        for (int i = 0; i < numCourses; i++) {
            if(inDeg[i] == 0) {
                q.offer(i);
            }
        }

        //存放拓扑排序后的点
        int[] res = new int[numCourses];
        int index = 0;
        while (!q.isEmpty()) {
            int x = q.poll();
            res[index++] = x;
            for (int y : g[x]) {
                if (--inDeg[y] == 0) {
                    q.offer(y);
                }
            }
        }

        //判断数组中的元素个数是否与课程数相同,相同返回res数组,否则返回空数组
        return index == numCourses ? res : new int[0];
    }

    public static void main(String[] args) {
        LeetCode210 code = new LeetCode210();
        System.out.println(Arrays.toString(code.findOrder(2, new int[][]{{0, 1}, {1, 0}})));
    }
}
